plans = 0
board = [[2 for _ in range(5)] for _ in range(5)]
w, b = 0, 0


def isValid(x, y, value):
    if x == 4 and y == 0:
        i, j = x - 1, y + 1
        count = 0
        while 0 <= i < 5 and 0 <= j < 5:
            if board[i][j] == value:
                count += 1
            i -= 1
            j += 1
        if count == 4:
            return False
    if y == 4 and x == 4:
        i, j = x - 1, y - 1
        count = 0
        while 0 <= i < 5 and 0 <= j < 5:
            if board[i][j] == value:
                count += 1
            i -= 1
            j -= 1
        if count == 4:
            return False
    if x == 4:
        count = 0
        for i in range(4):
            if board[i][y] == value:
                count += 1
        if count == 4:
            return False
    if y == 4:
        count = 0
        for i in range(4):
            if board[x][i] == value:
                count += 1
        if count == 4:
            return False
    return True


def backtracking(col, row):
    global plans, w, b
    if row == col == 4 and w == b + 1:
        plans += 1
    for i in range(col, 5):
        for j in range(row, 5):
            for val in (0, 1):
                if not isValid(i, j, val): continue
                if val == 0:
                    w += 1
                else:
                    b += 1
                board[i][j] = val
                if row == 4:
                    backtracking(col + 1, 0)
                    if val == 0:
                        w -= 1
                    else:
                        b -= 1
                else:
                    backtracking(col, row + 1)
                    if val == 0:
                        w -= 1
                    else:
                        b -= 1


backtracking(0, 0)
print(plans)
